W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Mieszkańcy bajtockiej wyspy Abstynencja bardzo lubią piwo bezalkoholowe. Do tej pory piwo bezalkoholowe sprowadzano z Polski, ale w tym roku w jednym z miast na Abstynencji zostanie wybudowany browar. Wszystkie miasta wyspy leżą na wybrzeżu i są połączone autostradą obiegającą wyspę wzdłuż brzegu. Inwestor budujący browar zebrał informacje o zapotrzebowaniu na piwo, tj. ile cystern piwa trzeba codziennie dostarczyć do każdego z miast. Dysponuje także zestawieniem odległości pomiędzy miastami. Koszt transportu jednej cysterny na odległość 1 km wynosi 1 talar. Dzienny koszt transportu to suma, jaką trzeba wyłożyć, by do każdego miasta przetransportować z browaru tyle cystern, ile wynosi zapotrzebowanie w danym mieście. Jego wielkość zależy od miejsca położenia browaru. Inwestor chce zminimalizować koszty transportu piwa.
Napisz program, który:
W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba całkowita równa liczbie miast, . W każdym z kolejnych wierszy zapisana jest para nieujemnych liczb całkowitych oddzielonych pojedynczym odstępem. Liczby zapisane w -ym wierszu to odpowiednio zapotrzebowanie na piwo w mieście nr oraz odległość (w kilometrach) od miasta nr do następnego miasta na autostradzie. Kolejne miasta na autostradzie mają kolejne numery, po mieście nr leży miasto nr 1. Całkowita długość autostrady nie przekracza km. Zapotrzebowanie na piwo w żadnym mieście nie przekracza cystern.
Twój program powinien zapisać w pierwszym i jedynym wierszu standardowego wyjścia dokładnie jedną liczbę całkowitą równą minimalnemu dziennemu kosztowi transportu piwa.
Dla danych wejściowych:
6 1 2 2 3 1 2 5 2 1 10 2 3
poprawną odpowiedzią jest:
41
Autor zadania: Wojciech Guzicki.